package leetcode101.ch5;

//LC 215

import java.util.Arrays;
import java.util.Random;

/**
 * 1、辅助函数 int quickSelection(int[] nums, int l, int r)
 *    判断左边界num[l]在区间[l,r]中是第几小的数，假设是第K小的，就把num[l]的值放在第K+l个位置，
 *    同时保证K左边的数都小于num[k], K右边的数都大于等于num[k]
 *    最后返回k+l
 * 2、主函数，类似二分的做法
 *    首先转换一下，第K大位置 = length - 第K小位置( int target = nums.length - k)
 *    先看最左一个数字在数组中排第几 int index = quickSelection(nums, 0, nums.length -1)
 *    如果 index 小于 target， 则扔掉index左边的，因为index = l + l 所以丢弃后不用调整target
 *    如果 index 大于 target，扔掉index右边的
 *    index等于target就找到了
 */
public class KthLargestElement {
    private static Random random = new Random(System.currentTimeMillis());
    public int findKthLargest(int[] nums, int k) {
        int l = 0, r = nums.length - 1;
        int target = nums.length - k;
        while (l <= r) { //TODO 必须小于等于，否则长度为1的数组进不来
            int index = quickSelectionRandom(nums, l ,r);
            if (index == target) {
                return nums[index];
            }else if (index < target) {
                l = index + 1;
            }else {
                r = index - 1;
            }
        }
        return -1;
    }

    private int quickSelection(int[] nums, int l, int r) {
        int pivot = nums[l];
        int k = 0;
        for (int i = l; i <= r; i++) {
            if (nums[i] < pivot) {
                k++;
                swap(nums, i, k + l); //TODO 注意这里要写k+l；
            }
        }
        swap(nums, l, k + l);
        return k + l;
    }

    private int quickSelectionRandom(int[] nums, int l, int r) {
        int randomIndex = l + random.nextInt(r - l + 1); //TODO 这里要加1，因为右边界达不到
        swap(nums, l, randomIndex);
        return quickSelection(nums, l, r);
    }

    private void swap(int[] nums, int i, int j) {
        if (i == j) return;  //TODO 这句对性能很重要
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,4,5,1,3,5,9,2,3,7,12,4};
//        int k = new KthLargestElement().quickSelection(nums, 2, nums.length-1);
//        System.out.println(Arrays.toString(nums));
//        System.out.println(k);

        nums = new int[]{1};
        System.out.println(new KthLargestElement().findKthLargest(nums, 1));
    }
}
